import java.util.Arrays;
import java.util.Comparator;

/**
 * Created by L.jp
 * Description:俄罗斯套娃信封问题
 * 给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
 *
 * 当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
 *
 * 请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
 *
 * 注意：不允许旋转信封。

 * User: 86189
 * Date: 2022-05-03
 * Time: 17:08
 */
public class Solution {
    /*这还是一道求最长上升子序列的问题*/
    public static int maxEnvelopes(int[][] envelopes) {
        int n = envelopes.length;
        //先排序，按照宽度升序，宽度相同时按照高度升序
        Arrays.sort(envelopes, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                int ret=o1[0]-o2[0];
                return  ret==0 ? o2[1]-o1[1] : ret;
            }
        });
        //这个方法在题目中是会超出时间限制的，所以要用动态规划+二分法
//        int ret=1;
//        int [] dp=new int[n];
//        dp[0]=1;
//        for(int i = 1; i < n; i++){
//            dp[i]=1;
//            for(int j=0;j<i;j++){
//                //信封相等的时候，不能装进去，只能算一封
//                if(envelopes[i][1] > envelopes[j][1]){
//                    dp[i]=Math.max(dp[j]+1,dp[i]);
//                }
//            }
//            ret=Math.max(ret,dp[i]);
//        }
//        return  ret;
        
        //dp+二分法，dp数组存储最长上升子序列元素
        int[] dp=new int[n];
        int end=-1; //dp数组最后一个元素下标
        for(int i = 0; i < n; i++){
            if(i==0 || dp[end]<envelopes[i][1]){
                dp[++end] = envelopes[i][1];
            }else{
                int index=binarySearch(envelopes[i][1],dp,end);
                dp[index]=envelopes[i][1];
            }
        }
        return end+1;
    }
    public static  int binarySearch(int target,int[] dp,int end){
        int l=0;
        int r=end;
        while (l<r){
            int mid=(l+r)/2;
            if(dp[mid]<target){
                l=mid+1;
            }else{
                r=mid;
            }
        }
        return l;
    }
    
    public static void main(String[] args) {
        int[][] envelopes={{5,4},{6,4},{6,7},{2,3}};
        System.out.println(maxEnvelopes(envelopes));
    }
}
